#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
using namespace std;

//栈的基本操作：初始化、进栈、出栈、取栈顶元素...

//1. InitStack(&S) 初始化操作  操作结果：构造一个空栈 S

//2. DestoryStack(&S) 销毁操作  初始条件：栈S已存在  操作结果：栈S被销毁 

//3. StackEmpty(S) 判定S是否为空  初始条件：栈S已存在 操作结果：空栈True，非空False 

//4. StackLength(S) 求栈的长度 初始条件：栈S已存在 操作结果：返回S的元素个数，即栈的长度

//5. GetTop(S, &e) 取栈顶元素 初始条件：栈S已存在且非空 操作结果：用e返回S的栈顶元素 

//6. ClearStack(&S) 栈置空操作 初始条件：栈S已存在  操作结果：将S清为空栈 

//7. Push(&S, e) 入栈操作 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素 

//8. Pop(&S, &e) 出栈操作 初始条件：栈S已存在且非空 操作结果：删除S的栈顶元素an,并用e返回其值 

//存储方式：顺序栈，链栈 

//栈的顺序存储方式与一般的线性表的顺序存储结构完全相同
//		附设top指针，指示栈顶元素在顺序栈中的位置
//	   另设base指针, 指示栈底元素在顺序栈中的位置
//	   为了方便操作，通常top指示 真正的栈顶元素之上 的下标地址 
//		另外：用stacksize表示栈可使用的最大容量 
//  空栈：base == top
//  栈满：top - base == stacksize 

//栈满时的处理方法：
//1. 报错，返回操作系统
//2. 分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈 

//使用数组作为顺序栈存储方式的特点：简单、方便、但易产生溢出 (数组大小固定)
//上溢(overflow): 栈已经满，又要压入元素  上溢是一种错误，使问题的处理无法进行 
//下溢(underflow): 栈已经空，还要弹出元素 下溢一般认为是一种结束条件，即问题处理结束 

//顺序栈的定义：
#define SElemType int
#define MAXSIZE 10
#define Status int
#define OVERFLOW 0
#define ERROR 0
#define OK 1
#define TRUE true
#define FALSE false
typedef struct{
	SElemType *base; //栈底指针
	SElemType *top;  //栈顶指针 
	int stacksize;  //栈可用最大容量 
}SqStack;


//3.1顺序栈的初始化 
Status InitStack(SqStack &S){
	S.base = new SElemType[MAXSIZE];
//或者 S.base = (SElemType *)malloc(MAXSIZE * sizeof(SElemType));
	if(!S.base) exit(OVERFLOW);  //存储分配失败
	S.top = S.base;   //栈顶指针等于栈底指针 
	S.stacksize = MAXSIZE;
	return OK;
} 

Status StackEmpty(SqStack S){
	if(S.top == S.base) return TRUE;
	return FALSE;
}

int StackLength(SqStack S){
	return S.top - S.base;
}

//清空栈
Status ClearStack(SqStack &S){
	if(S.base) S.top = S.base;
	return OK;
} 

//销毁栈
Status DestoryStack(SqStack &S){
	if(S.base){
		delete(S.base);
		S.stacksize = 0;
		S.base = S.top = NULL;
	}
	return OK;
} 

//3.2顺序栈的入栈  
//(1)判断是否栈满 (2)元素e压入栈顶 (3)栈顶指针加1 
Status Push(SqStack &S, SElemType e){
	if(S.top-S.base == S.stacksize) return ERROR;
	*S.top++ = e; //相当于两步：*S.top = e; S.top++; 
	return OK;
} 

//3.3顺序栈的出栈
//(1)判断是否栈空 (2)栈顶指针减1 (3)获取栈顶元素e 
Status Pop(SqStack &S, SElemType &e){
	if(S.top == S.base) return ERROR;
	e = *--S.top; //相当于两步：--S.top; e = *S.top; 
	return OK;
} 

int main(void)
{
	SqStack myStack;
	InitStack(*&myStack);
	printf("%p\n%p\n",myStack.top,myStack.base);
	int stack_length = StackLength(myStack);
	printf("stack_length = %d\n", stack_length);
	Status is_empty = StackEmpty(myStack);
	printf("is_empty: %d\n", is_empty);
	puts("请输入您要创建的栈元素个数：");
	int num,i=1;
	cin>>num;
	while(i<=num){
		SElemType e;
		printf("请输入第%d个元素：", i); 
		i++;
		cin>>e;
		Push(*&myStack, e);
		stack_length = StackLength(myStack);
		printf("stack_length = %d\n", stack_length);
	}
	printf("-----------\n开始出栈\n");
	while(num){
		num--;
		SElemType e;
		Pop(*&myStack, *&e);
		printf("%d出栈了\n",e);
	}
	return 0;
} 